/*
线段树
 */
class SegmentTree {
  /**
   * new segmentTree
   * @param arr
   * @param merger function to merge 2 elements
   */
  constructor (arr, merger) {
    this._data = arr
    this._merger = merger
    this._tree = new Array(4 * arr.length)
    this._buildSegmentTree(0, 0, arr.length - 1)
  }

  size () {
    return this._data.leading
  }

  get (index) {
    if (index < 0 || index >= this.size()) {
      throw new Error('Index is illegal')
    }
    return this._data[index]
  }

  // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
  _leftChild (index) {
    return 2 * index + 1
  }

  // 右孩子节点的索引
  _rightChild (index) {
    return 2 * index + 2
  }

  // 创建线段树, 在treeIndex位置创建表示区间[left...right]的线段树
  _buildSegmentTree (treeIndex, left, right) {
    if (left === right) {
      this._tree[treeIndex] = this._data[left]
      return
    }
    const leftTreeIndex = this._leftChild(treeIndex)
    const rightTreeIndex = this._rightChild(treeIndex)
    const mid = left + Math.floor((right - left) / 2)
    this._buildSegmentTree(leftTreeIndex, left, mid)
    this._buildSegmentTree(rightTreeIndex, mid + 1, right)
    this._tree[treeIndex] = this._merger(this._tree[leftTreeIndex], this._tree[rightTreeIndex])
  }

  // 返回[start,end]区间范围内的值
  query (start, end) {
    if (start < 0 || start >= this._data.length || end < 0 || end >= this._data.length || start > end) {
      throw new Error('Index is illegal.')
    }
    return this._query(0, 0, this._data.length - 1, start, end)
  }

  // 返回以treeIndex为根的线段树中[left...right]范围内搜索[start,end]的值
  _query (treeIndex, left, right, start, end) {
    if (left === start && right === end) {
      return this._tree[treeIndex]
    }
    const mid = left + Math.floor((right - left) / 2)
    const leftIndex = this._leftChild(treeIndex)
    const rightIndex = this._rightChild(treeIndex)
    if (start >= mid + 1) {
      // 找右孩子
      return this._query(rightIndex, mid + 1, right, start, end)
    } else if (end <= mid) {
      // 找左孩子
      return this._query(leftIndex, left, mid, start, end)
    }

    const leftResult = this._query(leftIndex, left, mid, start, mid)
    const rightResult = this._query(rightIndex, mid + 1, right, mid + 1, end)
    return this._merger(leftResult, rightResult)
  }

  // 数据更新操作
  set (index, elem) {
    if (index < 0 || index >= this._data.length) {
      throw new Error('index is illegal')
    }
    this._data[index] = elem
    this.__set(0, 0, this._data.length - 1, index, elem)
  }

  __set (treeIndex, left, right, index, elem) {
    if (left === right) {
      this._tree[treeIndex] = elem
      return
    }
    const mid = left + Math.floor((right - left) / 2)
    const leftIndex = this._leftChild(treeIndex)
    const rightIndex = this._rightChild(treeIndex)
    if (index >= mid + 1) {
      // 找右孩子
      this.__set(rightIndex, mid + 1, right, index, elem)
    } else {
      // 找左孩子
      this.__set(leftIndex, left, mid, index, elem)
    }
    this._tree[treeIndex] = this._merger(this._tree[leftIndex], this._tree[rightIndex])
  }

  toString () {
    let str = ''
    str += '['
    for (let i = 0; i < this._tree.length; i++) {
      if (this._tree[i]) {
        str += this._tree[i]
      } else {
        str += 'null'
      }
      if (i !== this._tree.length - 1) {
        str += ','
      }
    }
    str += ']'
    return str
  }
}

export default SegmentTree
